package Sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int A[] = {1, 6, 9, 2, 3, 1, 5, 4,123,545,0,45,25,48,2,8,42,8,5};
        quickSort(A, 0, A.length-1);
        System.out.println(Arrays.toString(A));
        int B[] = {1, 6, 9, 2, 3, 1, 5, 4,123,545,0,45,25,48,2,8,42,8,5};
        sortMy(B,0,B.length-1);
        System.out.println(Arrays.toString(B));

    }

    public static void quickSort(int[] A, int left, int right) {

        if (left < right) {
            // 一次划分
            int mid = partion(A, left, right);
            quickSort(A, 0, mid - 1);
            quickSort(A, mid + 1, right);
        }
    }

    public static void swap(int[] A, int l, int r) {
        int tmp = A[l];
        A[l] = A[r];
        A[r] = tmp;

    }

    public static int partion(int[] a, int left, int right) {
        // 轴值,默认选取数组的第一个数字
        while (left < right) {
            while (left < right && a[left] <= a[right]) {
                right--;
            }
            if (left < right) {
                swap(a, left, right);
            }
            while (left < right && a[left] <= a[right]) {
                left++;
            }
            if (left < right) {
                swap(a, left, right);
            }
        }
        return left;
    }

    public void quickSort2(int[] a, int start, int end) {
        if (start < end) {
            int baseNum = a[start];//选基准值
            int midNum;//记录中间值
            int i = start;
            int j = end;
            do {
                while ((a[i] < baseNum) && i < end) {
                    i++;
                }
                while ((a[j] > baseNum) && j > start) {
                    j--;
                }
                if (i <= j) {
                    midNum = a[i];
                    a[i] = a[j];
                    a[j] = midNum;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (start < j) {
                quickSort2(a, start, j);
            }
            if (end > i) {
                quickSort2(a, i, end);
            }
        }
    }


    public void sort(int[] a,int low,int high){
        int start = low;
        int end = high;
        int key = a[low];


        while(end>start){
            //从后往前比较
            while(end>start&&a[end]>=key)  //如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //从前往后比较
            while(end>start&&a[start]<=key)//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            //此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
        }
        //递归
        if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
        if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
    }


    public static void sortMy(int[] A ,int left ,int right){
        int begin = left;
        int end = right;

        int key = A[begin];
        while(left < right){
            while (left<right && key <= A[right]){
                right -- ;
            }
            if (left<right){
                int tmp = A[right];
                A[right] = key;
                A[left] = tmp;
            }

            while (left<right && key >= A[left]){
                left ++ ;
            }
            if (left<right){
                int tmp = A[left];
                A[left] = key;
                A[right] = tmp;
            }
        }
        if(begin < left) sortMy(A,begin,left-1);
        if(end > left) sortMy(A,right+1,end);
    }

}

